// @algorithm @lc id=100281 lang=cpp
// @title ji-qi-ren-de-yun-dong-fan-wei-lcof

#include "algm/algm.h"
#include <iostream>
#include <string>
#include <vector>
using namespace std;
class Solution {
    // @test(3, 2, 17)=6
    // @test(3, 2, 17)=6
    // @test(3, 2, 17)=6
public:
    vector<int> direction{0, 1, 0};
    int movingCount(int m, int n, int k) {
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        vector<vector<bool>> reach(m, vector<bool>(n, false));
        int ans = 0;
        backtracking(0, 0, m, n, k, visited, reach);
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (reach[i][j]) {
                    ++ans;
                }
            }
        }
        return ans;
    }

    // 回溯
    void backtracking(int i, int j, int m, int n, int k, vector<vector<bool>> &visited, vector<vector<bool>> &reach) {
        int sum_i = numSum(i);
        int sum_j = numSum(j);
        if (i >= m || j >= n || sum_i + sum_j > k || visited[i][j]) {
            return;
        }
        visited[i][j] = true;
        reach[i][j] = true;
        for (int z = 0; z < 2; ++z) {
            int x = i + direction[z];
            int y = j + direction[z + 1];
            backtracking(x, y, m, n, k, visited, reach);
        }
    }

    // 数位求和
    int numSum(int n) {
        int sum = 0;
        while (n) {
            sum += (n % 10);
            n /= 10;
        }
        return sum;
    }
};
